#include <stdio.h>
#include <stdlib.h>           //malloc() 需要 stdlib.h 库
#include "../../include/type_list.h"

//初始化线性表
Status InitList(List & L){
    //使用 malloc 动态分配一段内存，构造一个空的线性表      
    //malloc 函数：void * malloc(size_t  size);
    L.elem = (ElemType *) malloc (LIST_INIT_SIZE * sizeof (ElemType));
    if (! L.elem) exit (OVERFLOW);   //存储分配失败 
    L.length = 0; //空表长度为 0 
    L.listsize= LIST_INIT_SIZE;     //初始存储容量 
    return OK;
}// Initlist

//求表长
int Listlength(List L){
    return L.length;
}

//获取 L 中第 i 个元素
Status GetElem(List & L,int i, int & ele){ // i 是从 1 开始的
    if ((i < 1) || (i > L.length)) return ERROR;
    ele = *(L.elem + i - 1); //或写成 ele = L.elem[i - 1]
    return OK;
}

//定位线性表中使得 compare() 函数返回 true 的元素 e 的位置，其中 compare 是一个函数指针
int LocateElem(List L, ElemType e, Status(* compare)(ElemType,ElemType)){
    
    ElemType * p;
    int i = 1;
    p = L.elem;

    //一直找到 *p 和 e 不相等的 i 值
    while(i <= L.length && !compare(*p ++,e))
        ++i;
    
    //如果 i > L.length 说明 L.length = 0，则返回 0
    if(i <= L.length)
        return i;
    else
        return 0;
}

//依次对工的每个数据元素调用函数 visit，一旦 visit（）失败，则操作失败。
Status ListTraverse(List l,void (* vi) (ElemType *)){
    ElemType * p;
    int i;
    p = l.elem;
    for(i = 1;i <= l.length;i++)
        vi(p++);
    return OK;
}

Status equal(ElemType a,ElemType b){
    if(a == b)
        return OK;
    else
        return ERROR;
}

//线性表的插入:将 e 插入 L 的第 i 个位置处
Status ListInsert (List &L, int i, ElemType e){    //整个Sqlist &L，的 Sqlist & 表示 C++ 中的引用，所有可以直接 L.

    //在顺序线性表工中第 i 个位置（从 1 开始）之前插入新的元素 e, 
    //i 的合法值为 1 ≤ i ≤ ListLength_Sq (L) + 1，在第 ListLength_Sq (L) + 1 之前就是在整个线性表的最后
    if (i < 1 || i > L.length + 1) return ERROR;        // i 值不合法

    if (L.length >= L.listsize){                  
        //当前存储空间已满，增加分配
        //void *realloc(void * ptr, size_t  size); realloc()函数将旧空间释放掉并申请一个新空间，保证旧空间的数据会复制到新空间中，可以将小空间的数据放到大空间中，数据不会丢失但是不保证多出来的空间清零
        ElemType * newbase = (ElemType *) realloc (L.elem, (L.listsize + LISTINCREMENT) * sizeof (ElemType)); 
        if (! newbase) exit (OVERFLOW);                 //存储分配失败 
        L.elem = newbase;                               //新基址 
        L.listsize += LISTINCREMENT;                    //增加存储容量
    }

    //a[i] 的解释：a[i] = *(a + i)，而 L.elem 是分配的首地址，所以 L.elem[i - 1] = * (L.elem + i - 1)，即索引为 i - 1 的元素的值
    ElemType * q = & (L.elem[i - 1]);                               //q 为插入位置，因为 c 语言索引从 0 开始，索引第 i 个元素的索引为 i - 1

    //倒着往前循环，否则后边的元素会将前边的覆盖
    ElemType * p = 0;
    for(p = &(L.elem[L.length - 1]); p >= q; --p) 
        * (p + 1) = * p;                                //插入位置及之后的元素右移

    * q = e;                                            //插入 e
    ++ L.length;                                        //表长增 1

    return OK;

}// ListInsert_Sq

//线性表的合并:将 La 和 Lb 的数据合并到空 Lc 中
void Mergelist (List La, List Lb, List &Lc){

    //已知线性表 La 和 Lb 中的数据元素按值非递减排列
    //归并 La 和 Lb 得到新的线性表 Lc, Lc 的数据元素也按值非递减排列

    InitList(Lc);

    //i 是 La 的元素位置，j 是 Lb 的元素位置，k 是 Lc 的元素位置，都从 1 开始
    int i,j,k;
    i = j = 1; k = 0;

    int La_Len = Listlength(La); 
    int Lb_Len = Listlength (Lb);

    int ai = 0;
    int bj = 0;

    while ((i <= La_Len) && (j <= Lb_Len)) { //La 和 Lb 均非空 

        //获取 La 中的第 i 个元素赋值给 ai
        GetElem (La, i, ai); 

        //获取 Lb 中的第 j 个元素赋值给 bj
        GetElem (Lb,j, bj);

        //如果 ai 比 bj 小，那么把 ai 插入到 Lc 中，否则把 bj 插入到 Lc 中
        if  (ai <= bj) {
            ListInsert (Lc, ++k, ai); ++i; 
        }else{
            ListInsert (Lc, ++k, bj); ++j;
        };
    }

    //后边这两个循环只执行一个
    //如果 i 还没到 La 的最后，则把 La 剩下的元素 insert 到 Lc 中
    while (i <= La_Len){
        GetElem (La, i++, ai);
        ListInsert (Lc, ++k, ai);
    }

    //如果 i 还没到 Lb 的最后，则把 Lb 剩下的元素 insert 到 Lc 中
    while (j <= Lb_Len ) {
        GetElem(Lb, j++, bj);
        ListInsert(Lc, ++k, bj);
    }

}// Mergelist

//线性表的并集，将 Lb 合并到 La，因为 union 是关键字，所以方法名不再用 union，而用 Union
void Union (List & La, List Lb){
    //将所有在线性表 Lb 中但不在 La 中的数据元素插入到 La 中
    //求线性表的长度
    int La_Len = Listlength (La); 
    int Lb_Len = Listlength (Lb);

    for (int i = 1; i <= Lb_Len; i ++){

        ElemType e;
        
        //取 Lb 中第 i 个数据元素赋给 e
        GetElem (Lb, i, e);            
        
        //如果 La 中没有元素和 e 相等则将 e 插入到 La 中
        if (!LocateElem (La, e, equal))    //Locate elem : 定位元素
            ListInsert (La, ++ La_Len, e); //La 中不存在和 e 相同的数据元素，则插入之
    }
}//union
